/*
	aco-netdesign -- Ant colony optimization solution to network design problem

	Copyright (C) 2008 Jeffrey Sharkey, http://jsharkey.org/
	
	Developed by Jeffrey Sharkey as part of his thesis work at Montana State
	University. His work was sponsored by the Western Transportation Institute,
	and was guided by advisor Doug Galarus. Other valuable guidance was
	provided by Dr. Bill Jameson and Gary Schoep. 

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.
	
	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#pragma once

#include <math.h>
#include <assert.h>

#include <iostream>
#include <fstream>
#include <sstream>

#include <string>
#include <list>
#include <map>
#include <bitset>

using namespace std;

#define MAX_BANDWIDTH 65536

#define LARGE_COST 65536
#define SMALL_COST -65536

#define MAXID 65536*32
#define NEARMAXID MAXID*3/4
#define MAXID2 MAXID*MAXID


#include "util.h"


class Graph;



class Tagged {
public:
	static int nextid;
	int id;
	
	inline Tagged() {
		assert(nextid < MAXID);
		id = nextid++;
	}
	
	virtual inline ~Tagged() {
	}
	
	inline bool operator==(const Tagged &t) const {
		return t.id == id;
	}

};


template<class T> class ulist : public list<T> {
public:
	bitset<MAXID> flags;
	
	inline void insert(T t) {
		if(t == NULL) return;

		// add tagged item to list only if it doesnt exist
		Tagged* tagged = (Tagged*)t;
//cout << "trying id=" << tagged->id << endl;
//fflush(stdout);
		if(flags[tagged->id]) return;
		flags[tagged->id] = true;
		push_back(t);
	}
	
	inline void merge(ulist<T> u) {
		typename ulist<T>::iterator it;
		for(it = u.begin(); it != u.end(); it++) {
			insert(*it);
		}
	}
	
	inline bool contains(T t) {
		// check to see if list contains given item
		Tagged* tagged = (Tagged*)t;
		return flags[tagged->id];
	}

	inline void purge(T t) {
		// remove from list and the flags
		Tagged* tagged = (Tagged*)t;
		flags[tagged->id] = false;

		// find in our list and remove
		typename ulist<T>::iterator it;
		for(it = this->begin(); it != this->end(); it++) {
			if(*it == t) {
				erase(it);
				return;
			}
		}
	}
};


class Vertex : public Tagged {
public:
	int layer;
	double cost, bandwidth, radius;
	double lat, lon;
	double pref;
	bool terminal, root;
	string coverage;
	double* sens;
	Vertex* parent;
	
	Vertex(double lat_, double lon_, double cost_);
	Vertex(int layer_, double cost_, double bandwidth_, double lat_, double lon_, bool terminal_, bool root_);
	virtual ~Vertex();
	
	inline double distance(Vertex* v) {
		return distance(v->lat, v->lon);
	}

	inline double distance(double latb, double lonb) {
		double lat1 = toRadians(lat), lon1 = toRadians(lon),
			lat2 = toRadians(latb), lon2 = toRadians(lonb);
		
		return acos(sin(lat1) * sin(lat2) +
			cos(lat1) * cos(lat2) * cos(lon2 - lon1)) * RADIUS;
	}
	
	inline double euclidianDistance(Vertex* v) {
		return sqrt(pow(v->lat - lat, 2) + pow(v->lon - lon, 2));
	}
	
	inline string kmlString(double elev) {
		stringstream s;
		s.precision(8);
		s << lon << "," << lat << "," << elev;
		return s.str();
	}
	
	inline string kmlString() {
		return kmlString(0);
	}
	
};



class Edge : public Tagged {
public:
	Vertex* u;
	Vertex* v;
	double cost, bandwidth;
	double margin;

	Edge(Vertex* u_, Vertex* v_, double cost_);
	Edge(Vertex* u_, Vertex* v_, double cost_, double bandwidth_);
	Edge(Vertex* u_, Vertex* v_, double cost_, double bandwidth_, double margin_);
	virtual ~Edge();
	
	bool contains(Vertex* w);
	Vertex* adjacent(Vertex* w);
	
};



class Path {
public:
	Vertex* start;
	Vertex* end;
	Vertex* current;
	bool invalid;
	
	ulist<Vertex*> vertexes;
	ulist<Edge*> edges;
	
	Path(Vertex* start_, Vertex* end_);
	virtual ~Path();
	
	void follow(Edge* e);
	void merge(Path* p);
	bool finished();
	double cost();

	Edge* findEdge(Graph* g, Vertex* v);
	
	void serialize();
	void deserialize(Graph* g);
	
};




class Graph {
public:
	map<int,Vertex*> vertexes;
	map<int,Edge*> edges;
	
	Vertex* root;
	ulist<Vertex*> steiner;
	ulist<Vertex*> terminal;
	
	map<Vertex*, ulist<Edge*> > adjacentLookup;
	bool adjacentBuilt;
	
	Graph();
	virtual ~Graph();
	
	void addVertex(Vertex* v);
	void addEdge(Edge* e);
	ulist<Edge*> adjacent(Vertex* v);
	void buildAdjacent();
	void serializeCode(string filename);
	bool edgeExists(Vertex* u, Vertex* v);

	inline Edge* findEdge(Vertex* u, Vertex* v) {
		// check to see if edge exists between two points
		ulist<Edge*> outgoing = adjacent(u);
		ulist<Edge*>::iterator it;
		for(it = outgoing.begin(); it != outgoing.end(); it++) {
			Edge* e = (*it);
			if(e->contains(v))
				return e;
		}
		return NULL;
	}

	inline void saveVisual(ostream& out) {

// dump graph out to graphml file for later visualization

out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?><graphml xmlns=\"http://graphml.graphdrawing.org/xmlns/graphml\" xmlns:y=\"http://www.yworks.com/xml/graphml\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns/graphml http://www.yworks.com/xml/schema/graphml/1.0/ygraphml.xsd\">" << endl;
out << "<key id=\"d0\" for=\"node\" yfiles.type=\"nodegraphics\"/><graph id=\"G\" edgedefault=\"undirected\">" << endl;

// walk through and count up each layer type
cout << "saveVisual: counting up layers" << endl; cout.flush();
int counts[5] = { 0,0,0,0,0 };
map<int,Vertex*>::iterator it;
for(it = vertexes.begin(); it != vertexes.end(); it++) {
	Vertex* v = (*it).second;
	counts[v->layer]++;
}


// dump out all nodes in specific size
cout << "saveVisual: dumping out all vertexes" << endl; cout.flush();
int progress[5] = { 0,0,0,0,0 };
for(it = vertexes.begin(); it != vertexes.end(); it++) {
	Vertex* v = (*it).second;

	double x = 20000*(double)progress[v->layer] / (double)counts[v->layer];
	double y = 10000*(double)v->layer / 5;

	out << "<node id=\"n" << v->id << "\"><data key=\"d0\"><y:ShapeNode><y:Geometry x=\"" << x << "\" y=\"" << y << "\" width=\"15\" height=\"15\" /></y:ShapeNode></data></node>" << endl;

	progress[v->layer]++;
}


cout << "saveVisual: dumping out all edges" << endl; cout.flush();
map<int,Edge*>::iterator j;
for(j = edges.begin(); j != edges.end(); j++) {
	Edge* e = (*j).second;
	out << "<edge source=\"n" << e->u->id << "\" target=\"n" << e->v->id << "\"/>" << endl;

}

out << "</graph></graphml>" << endl;



	}


	inline void perturbCosts() {

// used to slightly perturb weights when using the approximation algorithm

//srand(1);

map<int,Vertex*>::iterator i;
for(i = vertexes.begin(); i != vertexes.end(); i++) {
	Vertex* v = (*i).second;
//	v->cost += 0.001*(double)rand()/(double)RAND_MAX;
	v->cost += 0.001*mt_rand();
}

map<int,Edge*>::iterator j;
for(j = edges.begin(); j != edges.end(); j++) {
	Edge* e = (*j).second;
//	e->cost += 0.001*(double)rand()/(double)RAND_MAX;
	e->cost += 0.001*mt_rand();
}





	}
	
	
};


class Lookup {
public:
	Graph* g;

	double* table;
	int width, size;
	bool filled;

	Lookup(Graph* g_);
	virtual ~Lookup();
	
	void set(int i, int j, double value);
	void set(Vertex* u, Vertex* v, double value);
	double get(int i, int j);
	double get(Vertex* u, Vertex* v);
	
	void load(istream& in);
	void save(ostream& out);
	
	Path* shortestPath(Vertex* u, Vertex* v);
	
};



Graph* buildType3(istream& in, int min, int max, int total);
Lookup* buildFloyd(Graph* g);

Vertex* find(ulist<Vertex*> vertexes, int id);
Edge* find(ulist<Edge*> edges, int id);

//bool contains(ulist<Vertex*> vertexes, Vertex* v);
//bool contains(ulist<Edge*> edges, Edge* e);


